# LeetCode 69、x 的平方根
# 一、题目描述
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 2^31 - 1
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：wzb_3377
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// x 的平方根（LeetCode 69）：https://leetcode.cn/problems/sqrtx/
class Solution {
public int mySqrt(int x) {
// 需要寻找出一个数 ans ，使得 ans * ans <= x ，并且 ans 总是尽可能更大
// 于是，开始在 [ 0 , x ] 这个区间中去查找
// 在查找过程中，不断的去缩小区间
// 左区间开始位置为 0
int left = 0 ;
// 右区间开始位置为 x
int right = x ;
// 算法平方根的结果，一开始为一个不可能的数 -1
int ans = -1;
// 开始在区间中查找
while (left <= right) {
// 先定位中间元素
int mid = left + (right - left) / 2;
// 由于 x 的范围能到达 int 的最大值
// 所以 mid 也有可能很大，导致 mid * mid 超过 int 的范围
// 因此使用 long
// 判断 mid 是否符合要求
// 1、如果发现不够
if ((long) mid * mid <= x) {
// 保留结果
ans = mid;
// 同时，可以舍去 left 左边的所有元素
left = mid + 1;
// 2、如果发现超过
} else {
// 同时，可以舍去 right 右边的所有元素
right = mid - 1;
}
}
// 返回结果
return ans;
}
}
# **2、**C++ 代码
class Solution {
public:
int mySqrt(int x) {
// 需要寻找出一个数 ans ，使得 ans * ans <= x ，并且 ans 总是尽可能更大
// 于是，开始在 [ 0 , x ] 这个区间中去查找
// 在查找过程中，不断的去缩小区间
// 左区间开始位置为 0
int left = 0 ;
// 右区间开始位置为 x
int right = x ;
// 算法平方根的结果，一开始为一个不可能的数 -1
int ans = -1;
// 开始在区间中查找
while (left <= right) {
// 先定位中间元素
int mid = left + (right - left) / 2;
// 由于 x 的范围能到达 int 的最大值
// 所以 mid 也有可能很大，导致 mid * mid 超过 int 的范围
// 因此使用 long
// 判断 mid 是否符合要求
// 1、如果发现不够
if ((long) mid * mid <= x) {
// 保留结果
ans = mid;
// 同时，可以舍去 left 左边的所有元素
left = mid + 1;
// 2、如果发现超过
} else {
// 同时，可以舍去 right 右边的所有元素
right = mid - 1;
}
}
// 返回结果
return ans;
}
};
# 3、Python 代码
class Solution:
def mySqrt(self, x: int) -> int:
# 需要寻找出一个数 ans ，使得 ans * ans <= x ，并且 ans 总是尽可能更大
# 于是，开始在 [ 0 , x ] 这个区间中去查找
# 在查找过程中，不断的去缩小区间
# 左区间开始位置为 0
left = 0
# 右区间开始位置为 x
right = x
# 算法平方根的结果，一开始为一个不可能的数 -1
ans = -1
# 开始在区间中查找
while left <= right :
# 先定位中间元素
mid = left + (right - left) // 2
# 由于 x 的范围能到达 的最大值
# 所以 mid 也有可能很大，导致 mid * mid 超过 的范围
# 因此使用 long
# 判断 mid 是否符合要求
# 1、如果发现不够
if mid * mid <= x :
# 保留结果
ans = mid
# 同时，可以舍去 left 左边的所有元素
left = mid + 1
# 2、如果发现超过
else :
# 同时，可以舍去 right 右边的所有元素
right = mid - 1
# 返回结果
return ans
# 四、复杂度分析
- 时间复杂度：O*(log*x)，即为二分查找需要的次数。
- 空间复杂度：O(1)。